package List;

/**
 * 148.排序链表
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 */
public class sortList {
    /**
     * hot100一刷
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }


    /**
     * hot100二刷
     */
    public ListNode sortList2(ListNode head) {
        if (head == null || head.next == null)
            return head;

        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = head;
        while (fast.next != slow) {
            fast = fast.next;
        }
        fast.next = null;
        ListNode l1 = sortList2(head);
        ListNode l2 = sortList2(slow);
        return mergesort(l1, l2);
    }

    public ListNode mergesort(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null)
            return l1 == null ? l2 : l1;
        if (l1.val <= l2.val) {
            l1.next = mergesort(l1.next, l2);
            return l1;
        } else {
            l2.next = mergesort(l1, l2.next);
            return l2;
        }
    }
}
